/*
 * CCVisu is a tool for visual graph clustering
 * and general force-directed graph layout.
 * This file is part of CCVisu.
 *
 * Copyright (C) 2005-2012  Dirk Beyer
 *
 * CCVisu is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * CCVisu is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with CCVisu; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Please find the GNU Lesser General Public License in file
 * license_lgpl.txt or http://www.gnu.org/licenses/lgpl.txt
 *
 * Dirk Beyer    (firstname.lastname@uni-passau.de)
 * University of Passau, Bavaria, Germany
 */
package org.sosy_lab.ccvisu.clustering;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertTrue;

import java.util.List;

import org.junit.Test;
import org.sosy_lab.ccvisu.graph.GraphData;
import org.sosy_lab.ccvisu.graph.GraphVertex;
import org.sosy_lab.ccvisu.graph.Group;

import com.google.common.collect.Lists;

public class ClustererMinDistPercTest {

  /**
   * Create one vertex/node for the test graph.
   * @param uniqueName
   * @param posX  Position on the x axis.
   * @param posY  Position on the y axis.
   * @param posZ  POsition on the z axis.
   * @return
   */
  private GraphVertex createTestVertex (String uniqueName, int posX, int posY, int posZ) {
    GraphVertex vertex = new GraphVertex(uniqueName);
    vertex.getPosition().x = posX;
    vertex.getPosition().y = posY;
    vertex.getPosition().z = posZ;

    return vertex;
  }

  /**
   * Create a test graph layout (without edges).
   * @return  Graph
   */
  public GraphData createTestGraph1() {
    GraphData graph = new GraphData();
    GraphVertex[] vertices = {
      // Cluster 1
      createTestVertex("V1", 1, 0, 0),
      createTestVertex("V2", 3, 0, 0),
      createTestVertex("V3", 4, 0, 0),

      // Cluster 2
      createTestVertex("V4", 10, 0, 0),
      createTestVertex("V5", 11, 0, 0),
      createTestVertex("V6", 13, 0, 0),

      // Cluster 3
      createTestVertex("V7", 21, 0, 0),
      createTestVertex("V8", 23, 0, 0),
      createTestVertex("V9", 25, 0, 0),

      // Cluster 4
      createTestVertex("V10", 41, 0, 0),
      createTestVertex("V11", 42, 0, 0)
    };

    // Represents the following graph:
    // o . o o | . . . . O o . o . | . . . . | o . o . O . . . . | . . . . | . . . . | o o . . |

    graph.setVertices(Lists.newArrayList(vertices));

    return graph;
  }

  /**
   * Create a test graph layout (without edges).
   * @return  Graph
   */
  public GraphData createTestGraph2() {
    GraphData graph = new GraphData();
    GraphVertex[] vertices = {
      // Cluster 1
      createTestVertex("V1", 1, 0, 0),
      createTestVertex("V2", 2, 0, 0),
      createTestVertex("V3", 3, 0, 0),

      // Cluster 2
      createTestVertex("V4", 10, 0, 0),
      createTestVertex("V5", 11, 0, 0),
      createTestVertex("V6", 12, 0, 0),

      // Cluster 3
      createTestVertex("V7", 21, 0, 0),
      createTestVertex("V8", 22, 0, 0),
      createTestVertex("V9", 23, 0, 0),

      // Cluster 4
      createTestVertex("V10", 41, 0, 0),
      createTestVertex("V11", 42, 0, 0)
    };

    // Represents the following graph:
    // o o o . | . . . . O o o . . | . . . . | o o o . | . . . . | . . . . | . . . . | o o . . |

    graph.setVertices(Lists.newArrayList(vertices));

    return graph;
  }


  /**
   * Create a test graph layout (without edges).
   * @return  Graph
   */
  public GraphData createTestGraph3() {
    GraphData graph = new GraphData();
    GraphVertex[] vertices = {
      // Cluster 1
      createTestVertex("V1", 1, 0, 0),
      createTestVertex("V2", 2, 0, 0),
      createTestVertex("V3", 3, 0, 0),

      // Cluster 2
      createTestVertex("V4", 11, 0, 0),
      createTestVertex("V5", 12, 0, 0),
      createTestVertex("V6", 13, 0, 0)
    };

    // Represents the following graph:
    // o o o . | . . . . | o o o . |

    graph.setVertices(Lists.newArrayList(vertices));

    return graph;
  }

  /**
   * Check if there is a partition containing all the given nodes.
   * @param partitions  List of partitions that are checked for the nodes.
   * @param nodeNames   Names of the nodes that should be contained in one partition.
   * @return
   */
  public boolean existNodesWithinOnePartition(List<Group> partitions, String[] nodeNames) {
    // TODO: Time complexity of this method could be optimized.
    for (Group g : partitions) {
      int contained = 0;
      for (GraphVertex n : g.getNodes()) {
        for (String s : nodeNames) {
          if (n.getName().equals(s)) {
            contained++;
          }
        }
      }

      if (contained == nodeNames.length) {
        return true;
      }
    }

    return false;
  }

  @Test
  public void createClustersOfLayout_NoHeuristic() {
    // Create the graph containing the test data.
    GraphData graph = createTestGraph1();

    // Create and parameterize the clustering algorithm.
    ClustererMinDistPerc clusterer = new ClustererMinDistPerc(graph, 4, 0, 1);

    // Run the clustering algorithm.
    List<Group> partitions = null;
    try {
      partitions = clusterer.createClustersOfLayout(graph);
    } catch (InterruptedException e) {
      assertTrue(false);
    }

    // Check the results.
    assertNotNull(partitions);
    assertEquals(4, partitions.size());
    assertTrue(existNodesWithinOnePartition(partitions, new String[] { "V10", "V11" }));
    assertTrue(existNodesWithinOnePartition(partitions, new String[] { "V7", "V8", "V9" }));
    assertTrue(existNodesWithinOnePartition(partitions, new String[] { "V4", "V5", "V6" }));
    assertTrue(existNodesWithinOnePartition(partitions, new String[] { "V1", "V2", "V3" }));
  }

  @Test
  public void createClustersOfLayout_UsingHeuristic() {
    // Create the graph containing the test data.
    GraphData graph = createTestGraph1();

    // Create and parameterize the clustering algorithm.
    ClustererMinDistPerc clusterer = new ClustererMinDistPerc(graph,
        4 /* Number of clusters. In general the stop parameter may case more than this. */,
        0.10 /* Max distance percent to auto merge.
         * 0.05 = 5% = All clusters within a distance of 5% of
         * the diagonal of the graph are merged without recalculating
         * there distances after each merge.
         */,
        1 /* Only merge clusters having a distance less than.
         * 1 = 100% = All clusters are within this distance.
         */
        );

    // Run the clustering algorithm.
    List<Group> partitions = null;
    try {
      partitions = clusterer.createClustersOfLayout(graph);
    } catch (InterruptedException e) {
      assertTrue(false);
    }

    for (Group group : partitions) {
      System.out.print(group.getName() + ": ");
      for (GraphVertex vertex : group.getNodes()) {
        System.out.print(vertex.getName() + ", ");
      }
      System.out.println();
    }

    // Check the results.
    assertNotNull(partitions);
    assertEquals(4, partitions.size());
    assertTrue(existNodesWithinOnePartition(partitions, new String[] { "V10", "V11" }));
    assertTrue(existNodesWithinOnePartition(partitions, new String[] { "V7", "V8", "V9" }));
    assertTrue(existNodesWithinOnePartition(partitions, new String[] { "V4", "V5", "V6" }));
    assertTrue(existNodesWithinOnePartition(partitions, new String[] { "V1", "V2", "V3" }));
  }
}
